package com.magic.interview.贪心.LC1414和为K的最少斐波那契数字数目;

/**
 * @author laoma
 * 参考：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-rgty8/
 * @create 2022-02-03 16:11
 */
public class Solution {
    public int findMinFibonacciNumbers(int k) {
        int a = 1;
        int b = 1;
        while (b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        int ans = 0;
        while (k!=0){
            if(k >= b){
                k-=b;
                ++ ans;
            }
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }
}
